#include<iostream>
#include "BinarySearchTree.h"
#include <vector>
#include <ctime>
using namespace std;

/// @brief 乱序函数
/// @tparam Comparable 
/// @param  oldArray 乱序前的数组
/// @param  newArray 乱序后的数组
template <typename Comparable>
void RandomArray(std::vector<Comparable> &oldArray,std::vector<Comparable> &newArray)
{
    for(int i = oldArray.size();i>0;i--)
    {
        srand(unsigned(time(NULL)));
    
        int index = rand()%i; //在0~i-1的范围内生成一个随机数
        
        newArray.push_back(oldArray[index]); //将对应下标的元素推入新数组

        oldArray.erase(oldArray.begin() + index); //从原数组中删除该元素
    }
}


/// @brief 使用BST排序算法对数组进行排序
/// @tparam Comparable 
/// @param _arr 需要排序的数组
/// @param _mode 有0和1两种输入，输入1时先对数组乱序处理
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
{
    /// 检查_mode输入是否合法，再根据输入对数组乱序处理
    
    if(_mode != 1 && _mode != 0) ///如果用户给出非法输入，输出警告并终止程序
    {
        cout << "Illegal mode!" << endl;
        exit(-1);
    }
    else if(_mode == 1) ///如果输入为1，对_arr进行乱序
    {
        typename std::vector<Comparable> newArray(0);
        RandomArray(_arr,newArray);
        _arr = newArray;
    }
    
    /// 新建bst，将数组中的元素按顺序插入bst中，在插入时完成排序
    BinarySearchTree<Comparable> bst;
    
    for(int i = 0 ; i < _arr.size() ; i++)
        bst.insert(_arr[i]);
    
    _arr.clear();
    bst.movetoarray(_arr);   
}

/// @brief 测试程序
/// @return 
int main()
{
    int n,mode;
    for(int j = 0;j < 8;j++){

      n = 5000 *(j / 4 + 1);
      mode = j % 4 != 0;

    /// 创建空向量并逆序插入n个整数 
    vector<int> intVector(0);
    for(int i = n ; i > 0 ; i--)
        intVector.push_back(i);

    /// 调用排序函数，并记录时间 
    clock_t Starttime = clock();
    BSTSorting(intVector,mode);
    clock_t Endtime = clock();

    /// 输出程序运行时间 
    cout << "Sorting time for " << "n = " << n << " and mode = "
    << mode << " : " << double(Endtime-Starttime) / CLOCKS_PER_SEC << "s" << endl;
    }
    return 0;
}
